package com.hw.algorithm.leetcode.string;

/**
 * @program: algorithm
 * @author: hewei
 * @date: 2023-04-26 14:26
 * <h>14. 最长公共前缀</h>
 * <p>
 *     编写一个函数来查找字符串数组中的最长公共前缀。
 *
 * 如果不存在公共前缀，返回空字符串 ""。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 *
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-common-prefix
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * </p>
 *
 **/
public class LeetCodeString14 {
    public static void main(String[] args) {
        String[] strs = {"flower","flow","floight"};
//        String[] strs = {"a"};
//        String[] strs = {"dog","racecar","car"};
        System.out.println(longestCommonPrefixProbe(strs));
    }

    /*逐步探测法：以第一个字符串的开头依次在其他字符串中尝试比对，只要有一个不满足就返回*/
    public static String longestCommonPrefixProbe(String[] strs) {
        String longstr="";
        for (int i=1; i<=strs[0].length();i++) {
            longstr=strs[0].substring(0,i);
            for (int j=1; j<strs.length;j++) {
                if (!strs[j].startsWith(longstr)){
                    return longstr.length()>=1 ? longstr.substring(0,longstr.length()-1) : "";
                }
            }
        }
        return longstr;
    }

    /*纵向字符扫描*/
    public static String longestCommonPrefixCharCmp(String[] strs) {
        String longstr="";
        int minLength=strs[0].length();
        for (int i=1; i<strs.length;i++) {
            if (minLength > strs[i].length()) {
                minLength = strs[i].length();
            }
        }
        for (int j=0; j < minLength;j++) {
            for (int k=0; k < strs.length;k++) {

            }

        }
        return longstr;
    }

}
